# -*- coding: utf-8 -*-

"""剑指 Offer II 090. 环形房屋偷盗
一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：
输入：nums = [0]
输出：0

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 1000"""

class Solution:
    """本题相对于上一题将链式街道改成环形街道，那么就有首尾不能同时偷的条件
    问题可以分解为两个，
        如果偷了第一个，从第3位开始到倒数第2位，能偷盗的最高金额
        如果没有偷第一个，从第2位开始到最后1位，能偷盗的最高金额
        两者再取最大值
        动态规划+递归"""
    def rob(self, nums) -> int:
        last = len(nums)-1
        if last < 3:
            return max(nums)
        if last == 3:
            return max(nums[0]+nums[2], nums[1]+nums[3])
        
        def init_table(last):
            return {
                last-2: max(nums[last-2]+nums[last], nums[last-1]),
                last-1: max(nums[last-1], nums[last]),
                last: nums[last]
            }

        def optimal(i, last, table):
            if i >= last-2:
                return table[i]
            
            if i+3 in table:
                forth = table[i+3]
            else:
                forth = optimal(i+3, last, table)
                table[i+3] = forth

            if i+2 in table:
                third = table[i+2]
            else:
                third = optimal(i+2, last, table)
                table[i+2] = third

            return max(nums[i]+third, nums[i+1]+forth)
        return max(optimal(0, last-1, init_table(last-1)), optimal(1, last, init_table(last)))


if __name__ == '__main__':
    so = Solution()
    print(so.rob([2,3,2]))
    print(so.rob([1,2,3,1]))
    print(so.rob([0]))
    print(so.rob([1,1,3,6,7,10,7,1,8,5,9,1,4,4,3]))
    print(so.rob([200,3,140,20,10]))
    print(so.rob([226,174,214,16,218,48,153,131,128,17,157,142,88,43,37,157,43,221,191,68,206,23,225,82,54,118,111,46,80,49,245,63,25,194,72,80,143,55,209,18,55,122,65,66,177,101,63,201,172,130,103,225,142,46,86,185,62,138,212,192,125,77,223,188,99,228,90,25,193,211,84,239,119,234,85,83,123,120,131,203,219,10,82,35,120,180,249,106,37,169,225,54,103,55,166,124]))
